package programmercarl.二叉树.找到值返回路径;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

public class Main {
    List<Integer> list=new ArrayList<>();
    public List<Integer> path(TreeNode root,int target) {
        travel(root,new ArrayList<>(),target);
        return list;
    }

    private void travel(TreeNode root,List<Integer> path,int target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        if (root.val == target) {
            list=path;
            return;
        }
        if (root.left != null) {
            travel(root.left,path,target);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            travel(root.right,path,target);
            path.remove(path.size() - 1);
        }
    }
}
